
/*
 *  Copyright 2021 籽籮籮 籵籮籮籯类籲籷籰
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 *  These are the four essential freedoms with GNU GPL software:
 *  1: freedom to run the program, for any purpose
 *  2: freedom to study how the program works, and change it to make it do what you wish
 *  3: freedom to redistribute copies to help your Free Software friends
 *  4: freedom to distribute copies of your modified versions to your Free Software friends
 *   ,           ,
 *  /             \
 * ((__-^^-,-^^-__))
 * `-_---'  `---_-'
 *  `--|o`   'o|--'
 *      \  `  /
 *       ): :(
 *       :o_o:
 *        "-"
 */

#include "config.h"

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "main.h"
#include "uniqnode.h"
#include "uniqstr.h"
#include "hier.h"


int yydebug = 0;

/* positioning mode of drawing used in pos.c */
int posmode = 1;

/* parser messages */
char parsermessage[256];

/* max y level */
int maxlevel = 0;

/* number of levels */
int nlevels = 0;

/* number of nodes at level */
int *nnodes_of_level = NULL;

/* number of edges between level n and n+1 */
int *nume = NULL;

/* level with most nodes */
int widestlevel = 0;

/* number of nodes at widest level */
int widestnnodes = 0;

/* max x of end drawing */
int maxx = 0;

/* max y of end drawing */
int maxy = 0;

/* width of positions */
int *wpos = NULL;

/* lists per pos. */
struct gml_nlist **posnodes = NULL;

/* height of levels */
int *hpos = NULL;

/* lists per level */
struct gml_nlist **levelnodes = NULL;


/* compare outgoing edges, looking at the to-node prosition */
static int
edgescompareout (const void *p, const void *q)
{
  struct gml_edge *l;
  struct gml_edge *r;
  struct gml_node *ll;
  struct gml_node *rr;
  int lll = 0;
  int rrr = 0;

  l = *(struct gml_edge **) p;
  r = *(struct gml_edge **) q;

  ll = l->to_node;
  rr = r->to_node;

  lll = ll->finx;
  rrr = rr->finx;

  return (lll - rrr);
}

/* compare incoming edges, looking at the from-node prosition */
static int
edgescomparein (const void *p, const void *q)
{
  struct gml_edge *l;
  struct gml_edge *r;
  struct gml_node *ll;
  struct gml_node *rr;
  int lll = 0;
  int rrr = 0;

  l = *(struct gml_edge **) p;
  r = *(struct gml_edge **) q;

  ll = l->from_node;
  rr = r->from_node;

  lll = ll->finx;
  rrr = rr->finx;

  return (lll - rrr);
}

/* calculate edge connections */
void
edgeconnections (struct gml_graph *g)
{
  struct gml_elist *ell;
  struct gml_nlist *lnl;
  int i = 0;

  if (g->edgelist == NULL)
    {
      /* no edges, nothing to do here */
      return;
    }

  /* mark vertical edges */
  ell = g->edgelist;

  while (ell)
    {
      ell->edge->vedge = 0;

      if ((ell->edge->from_node->finx + (ell->edge->from_node->bbx / 2)) ==
	  (ell->edge->to_node->finx + (ell->edge->to_node->bbx / 2)))
	{
	  /* mark edge as perfect vertical */
	  ell->edge->vedge = 1;
	}
      ell = ell->next;
    }

  /* make arrays with edges in every node */
  lnl = g->nodelist;

  while (lnl)
    {
      if (lnl->node->indegree > 1)
	{
	  /* check if enough size at node for edge placement */
	  if ((lnl->node->indegree * 3 + 15 + 15) < lnl->node->bbx)
	    {
	      lnl->node->iedges =
		(struct gml_edge **) calloc (1,
					     (sizeof (struct gml_edge *))
					     * lnl->node->indegree);
	      i = 0;
	      ell = lnl->node->incoming_e;
	      while (ell)
		{
		  lnl->node->iedges[i] = ell->edge;
		  i++;
		  ell = ell->next;
		}
	      qsort ((void *) lnl->node->iedges, (size_t) lnl->node->indegree,
		     (size_t) sizeof (struct gml_edge *), edgescomparein);
	      lnl->node->dx_iedges =
		((lnl->node->bbx - 15 - 15) / (lnl->node->indegree - 1));
	    }
	  else
	    {
	      lnl->node->iedges = NULL;
	      lnl->node->dx_iedges = 0;
	    }
	}

      if (lnl->node->outdegree > 1)
	{
	  if ((lnl->node->outdegree * 3 + 15 + 15) < lnl->node->bbx)
	    {
	      lnl->node->oedges =
		(struct gml_edge **) calloc (1,
					     (sizeof (struct gml_edge *))
					     * lnl->node->outdegree);
	      i = 0;
	      ell = lnl->node->outgoing_e;
	      while (ell)
		{
		  lnl->node->oedges[i] = ell->edge;
		  i++;
		  ell = ell->next;
		}
	      qsort ((void *) lnl->node->oedges,
		     (size_t) lnl->node->outdegree,
		     (size_t) sizeof (struct gml_edge *), edgescompareout);
	      lnl->node->dx_oedges =
		((lnl->node->bbx - 15 - 15) / (lnl->node->outdegree - 1));
	    }
	  else
	    {
	      lnl->node->oedges = NULL;
	      lnl->node->dx_oedges = 0;
	    }
	}

      lnl = lnl->next;
    }

  return;
}

/* clear number of edges between level n and N+1 */
void
clear_nume (void)
{
  if (nume)
    {
      free (nume);
    }
  nume = NULL;
  return;
}

/* free one record label info */
static void
clear_rlabel2 (struct gml_rl *info)
{
  int i = 0;
  if (info == NULL)
    {
      return;
    }
  for (i = 0; i < info->nparts; i++)
    {
      clear_rlabel2 (info->parts[i]);
    }
  free (info->parts);
  info->parts = NULL;
  free (info);
  return;
}

/* clear optional record labels */
void
clear_rlabel (struct gml_graph *g)
{
  struct gml_nlist *lnl = NULL;

  lnl = g->nodelist;

  while (lnl)
    {
      if (lnl->node->rlabel)
	{
	  clear_rlabel2 (lnl->node->rlabel);
	  lnl->node->rlabel = NULL;
	}
      lnl = lnl->next;
    }

  return;

}

/* clear arrays in/out edges in nodes */
void
clear_ioedges (struct gml_graph *g)
{
  struct gml_nlist *lnl = NULL;

  lnl = g->nodelist;

  while (lnl)
    {
      /* array with out edges */
      if (lnl->node->oedges)
	{
	  free (lnl->node->oedges);
	  lnl->node->oedges = NULL;
	}
      lnl->node->dx_oedges = 0;

      /* array with in edges */
      if (lnl->node->iedges)
	{
	  free (lnl->node->iedges);
	  lnl->node->iedges = NULL;
	}
      lnl->node->dx_iedges = 0;

      lnl = lnl->next;
    }

  return;
}

/* clear the s/t list of a node */
void
clear_stlist (struct gml_node *node)
{
  struct gml_elist *ell = NULL;
  struct gml_elist *ellnext = NULL;

  /* free outgoing edges */
  ell = node->outgoing_e;

  while (ell)
    {
      ellnext = ell->next;
      free (ell);
      ell = ellnext;
    }

  node->outgoing_e = NULL;
  node->outgoing_etail = NULL;
  node->outdegree = 0;

  /* free incoming edges */
  ell = node->incoming_e;

  while (ell)
    {
      ellnext = ell->next;
      free (ell);
      ell = ellnext;
    }

  node->incoming_e = NULL;
  node->incoming_etail = NULL;
  node->indegree = 0;

  return;
}

/* clear the s/t list of all nodes */
void
clear_stlist_all (struct gml_graph *g)
{
  struct gml_nlist *lnl = NULL;

  lnl = g->nodelist;

  while (lnl)
    {
      clear_stlist (lnl->node);
      lnl = lnl->next;
    }

  return;
}

/* clear nodelist, nodes and inside nodes */
void
clear_rawnodelist (struct gml_graph *g)
{
  struct gml_nlist *lnl = NULL;
  struct gml_nlist *nlnext = NULL;

  lnl = g->rawnodelist;

  while (lnl)
    {
      nlnext = lnl->next;
      free (lnl->node);
      lnl->node = NULL;
      free (lnl);
      lnl = nlnext;
    }

  g->nnodes = 0;

  return;
}

/* clear edgelist */
void
clear_rawedgelist (struct gml_graph *g)
{
  struct gml_elist *el = NULL;
  struct gml_elist *elnext = NULL;

  el = g->rawedgelist;

  while (el)
    {
      elnext = el->next;
      free (el->edge);
      el->edge = NULL;
      free (el);
      el = elnext;
    }

  g->nedges = 0;
  g->edgenum = 0;

  return;
}

/* clear nodelist, nodes and inside nodes */
void
clear_nodelist (struct gml_graph *g)
{
  struct gml_nlist *lnl = NULL;
  struct gml_nlist *nlnext = NULL;

  clear_stlist_all (g);

  lnl = g->nodelist;
  while (lnl)
    {
      nlnext = lnl->next;
      free (lnl->node);
      lnl->node = NULL;
      free (lnl);
      lnl = nlnext;
    }

  g->nnodes = 0;
  g->nodenum = 0;

  return;
}

/* clear single node list */
void
clear_singlenodelist (struct gml_graph *g)
{
  struct gml_nlist *lnl = NULL;
  struct gml_nlist *nlnext = NULL;

  lnl = g->singlenodelist;

  while (lnl)
    {
      nlnext = lnl->next;
      free (lnl);
      lnl = nlnext;
    }

  g->nsinglenodes = 0;

  return;
}

/* clear self-edges node list */
void
clear_selfedgesnodelist (struct gml_graph *g)
{
  struct gml_nlist *lnl = NULL;
  struct gml_nlist *nlnext = NULL;

  lnl = g->selfedgesnodelist;

  while (lnl)
    {
      nlnext = lnl->next;
      free (lnl);
      lnl = nlnext;
    }

  g->nselfedges = 0;

  return;
}

/* clear edgelist */
void
clear_edgelist (struct gml_graph *g)
{
  struct gml_elist *el = NULL;
  struct gml_elist *elnext = NULL;

  el = g->edgelist;

  while (el)
    {
      elnext = el->next;
      free (el->edge);
      el->edge = NULL;
      free (el);
      el = elnext;
    }

  return;
}

/* rebuild nodes st lists */
void
make_stlist (struct gml_graph *g)
{
  struct gml_elist *el = NULL;
  struct gml_edge *edge = NULL;
  struct gml_node *sn = NULL;
  struct gml_node *tn = NULL;
  struct gml_elist *ne = NULL;

  el = g->edgelist;

  while (el)
    {
      edge = el->edge;

      /* from/to nodes */
      sn = edge->from_node;
      tn = edge->to_node;
      ne = calloc (1, sizeof (struct gml_elist));

      if (ne == NULL)
	{
	  return;
	}

      ne->edge = edge;

      /* list of outgoing edges */
      if (sn->outgoing_e == NULL)
	{
	  sn->outgoing_e = ne;
	  sn->outgoing_etail = ne;
	}
      else
	{
	  sn->outgoing_etail->next = ne;
	  sn->outgoing_etail = ne;
	}

      sn->outdegree++;
      ne = calloc (1, sizeof (struct gml_elist));

      if (ne == NULL)
	{
	  return;
	}

      ne->edge = edge;
      /* list of incoming edges */
      if (tn->incoming_e == NULL)
	{
	  tn->incoming_e = ne;
	  tn->incoming_etail = ne;
	}
      else
	{
	  tn->incoming_etail->next = ne;
	  tn->incoming_etail = ne;
	}

      tn->indegree++;
      el = el->next;
    }

  return;
}

/* delete edge when replaced with a chain of edges */
void
del_edge (struct gml_graph *g, struct gml_elist *edgeel)
{
  struct gml_elist *elprev = NULL;
  struct gml_elist *el = NULL;
  struct gml_elist *elto = NULL;

  if (g->edgelist == NULL)
    {
      return;
    }

  if (edgeel == g->edgelist)
    {
      g->edgelist = g->edgelist->next;
      if (g->edgelisttail == edgeel)
	{
	  g->edgelisttail = NULL;
	}
      else
	{
	  el = g->edgelist;
	  elprev = el;
	  while (el)
	    {
	      elprev = el;
	      if (el->next == edgeel)
		{
		  break;
		}
	      el = el->next;
	    }
	  g->edgelisttail = elprev;
	}

      free (edgeel->edge);
      edgeel->edge = NULL;
      free (edgeel);
    }
  else
    {

      elto = edgeel->next;
      el = g->edgelist;

      elprev = el;

      while (el)
	{
	  elprev = el;
	  if (el->next == edgeel)
	    {
	      break;
	    }
	  el = el->next;
	}

      elprev->next = elto;
      if (g->edgelisttail == edgeel)
	{
	  g->edgelisttail = elprev;
	}

      free (edgeel->edge);
      edgeel->edge = NULL;
      free (edgeel);
    }

  return;
}

/* splits edgelabel edges into node->label->node */
void
edgelabels (struct gml_graph *g)
{
  struct gml_elist *el = NULL;
  struct gml_elist *elnext = NULL;
  struct gml_node *ln = NULL;
  char rev = 0;
  int ecolor = 0;
  int style = 0;
  char *fc = NULL;
  char *tc = NULL;

  if (g->nedgelabels == 0)
    {
      /* no edge labels, nothing todo here */
      return;
    }

  /* scan edges for edge labels */
  el = g->edgelist;

  while (el)
    {
      elnext = el->next;
      if (el->edge->elabel)
	{
	  g->maxid++;
	  /* edge attr. is-reversed */
	  rev = el->edge->reversed;
	  ecolor = el->edge->ecolor;
	  style = el->edge->style;
	  fc = el->edge->fcompass;
	  tc = el->edge->tcompass;
	  /* create label node */
	  add_new_dummynode (g, g->maxid);
	  /* mark this is a label node and set label text */
	  ln = uniqnodeid (g->maxid);
	  ln->elabel = 1;	/* mark this is a edgelabel */
	  ln->dummy = 0;
	  ln->nlabel = el->edge->elabel;
	  ln->startnode = el->edge->from_node->startnode;
	  /* create new edges with label node in between */
	  add_new_dummyedge (g, el->edge->from_node->id, g->maxid, rev,
			     ecolor, style, fc, tc);
	  add_new_dummyedge (g, g->maxid, el->edge->to_node->id, rev, ecolor,
			     style, fc, tc);
	  /* free old edge */
	  del_edge (g, el);
	}

      el = elnext;
    }

  return;
}



/* break cycle reversing last edge in it */
void
decycle (struct gml_node *n, int num)
{
  struct gml_elist *oute = NULL;

  if (n->done)
    {
      return;
    }

  /* this node is set */
  n->done = 1;

  /* uppdate dfs counter */
  n->num = ++num;

  /* check the outgoing edges of this node */
  oute = n->outgoing_e;

  while (oute)
    {
      /* if not done yet */
      if (oute->edge->to_node->done == 0)
	{
	  /* recursive */
	  decycle (oute->edge->to_node, num);
	}
      oute = oute->next;
    }


  return;
}

/* break cycles in the graph */
void
uncycle (struct gml_graph *g)
{
  struct gml_node *temp = NULL;
  struct gml_elist *enl = NULL;
  struct gml_nlist *lnl = NULL;
  int nrev = 0;

  /* build the s/tlist of a node */
  clear_stlist_all (g);
  make_stlist (g);

  /* revert cycles at the last edge in the chain */
  maxlevel = 0;


  lnl = g->nodelist;

  while (lnl)
    {
      lnl->node->num = 0;
      lnl->node->done = 0;
      lnl->node->y = -1;
      lnl = lnl->next;
    }

  lnl = g->nodelist;

  while (lnl)
    {

      if (lnl->node->done == 0)
	{
	  decycle (lnl->node, 0);
	}
      lnl = lnl->next;
    }



  /* now reverse the indicated edges */
  nrev = 0;

  /* scan the edges and reverse selected edges */
  enl = g->edgelist;
  while (enl)
    {
      /* do the actual edge reversing */
      if (enl->edge->to_node->num < enl->edge->from_node->num)
	{
	  printf ("%s(): to reverse edge from gml node=%d to gml node=%d\n",
		  __func__, enl->edge->from_node->id, enl->edge->to_node->id);
	  nrev++;
	  /* now swap the nodes in this edge. */
	  temp = enl->edge->from_node;
	  enl->edge->from_node = enl->edge->to_node;
	  enl->edge->to_node = temp;
	  enl->edge->reversed = 1;
	}
      else
	{
	  /* this edge is not changed. */
	  enl->edge->reversed = 0;
	}
      enl = enl->next;
    }

  printf ("reversed edges=%d\n", nrev);

  if (nrev)
    {
      /* build the in/out edges list of a node */
      clear_stlist_all (g);
      make_stlist (g);
    }

  return;
}

/* all edges downwards */
void
edgesdownwards (struct gml_graph *g)
{
  struct gml_elist *el = NULL;
  struct gml_node *tmpnode = NULL;
  struct gml_node *sn = NULL;
  struct gml_node *tn = NULL;
  struct gml_edge *edge = NULL;

  el = g->edgelist;

  while (el)
    {
      edge = el->edge;

      sn = edge->from_node;
      tn = edge->to_node;

      if (tn->y - sn->y < 0)
	{
	  if (0)
	    {
	      printf ("edgelen < 0 from %d->%d level %d->%d\n", sn->id,
		      tn->id, sn->y, tn->y);
	    }

	  /* swap */
	  tmpnode = tn;
	  el->edge->to_node = el->edge->from_node;
	  el->edge->from_node = tmpnode;

	  /* toggle the edge is reversed bit */
	  if (el->edge->reversed)
	    {
	      el->edge->reversed = 0;
	    }
	  else
	    {
	      el->edge->reversed = 1;
	    }
	}

      el = el->next;
    }


  /* rebuild the in/out edges lists at the nodes in the modified graph */
  maxlevel = 0;

  /* refresh st lists */
  clear_stlist_all (g);
  make_stlist (g);

  return;
}


/* add node as single node */
static void
add_selfedgenode (struct gml_graph *g, struct gml_node *node)
{
  struct gml_nlist *lnl = NULL;

  lnl = (struct gml_nlist *) calloc (1, sizeof (struct gml_nlist));

  lnl->node = node;

  if (g->selfedgesnodelist == NULL)
    {
      g->selfedgesnodelist = lnl;
      g->selfedgesnodelisttail = lnl;
    }
  else
    {
      g->selfedgesnodelisttail->next = lnl;
      g->selfedgesnodelisttail = lnl;
    }

  return;
}


/* set relative y rank level of a node.
 * uses incoming edges, not outgoing edges.
 * this is recursive and can casue stack smashing.
 */
static int
ylevelsdfs (struct gml_node *n)
{
  struct gml_elist *ine = NULL;
  int res = 0;
  int temp = 0;

  if (n->y >= 0)
    {
      /* already set */
      return (n->y);
    }

  /* check the list of incoming edges of this node */
  ine = n->incoming_e;

  if (ine == NULL)
    {
      /* nodes with no incoming edges at top. */
      n->y = 0;
    }
  else
    {

      /* init */
      res = 0;
      temp = 0;

      while (ine)
	{
	  /* recursive. */
	  temp = ylevelsdfs (ine->edge->from_node) + 1;
	  if (temp > res)
	    {
	      res = temp;
	    }
	  ine = ine->next;
	}

      n->y = res;
    }

  return (n->y);
}

/* set relative y level of all nodes */
void
ylevels (struct gml_graph *g)
{
  struct gml_elist *enl = NULL;
  struct gml_nlist *lnll = NULL;
  int temp = 0;

  /* run dfs to set the relative y level.
   * start with the nodes which are start nodes
   */

  /* init with value -1 meaning undefined value */
  lnll = g->nodelist;
  while (lnll)
    {
      lnll->node->y = -1;
      lnll = lnll->next;
    }

  lnll = g->nodelist;
  while (lnll)
    {
      /* start nodes start at rank level 0 at top of drawing */
      temp = ylevelsdfs (lnll->node);
      if (temp)
	{
	}
      lnll = lnll->next;
    }

  printf ("%s(): this are the relative y levels of the nodes:\n", __func__);
  lnll = g->nodelist;
  while (lnll)
    {
      printf ("  node %d gml=%d level=%d indegree=%d outdegree=%d\n",
	      lnll->node->nr, lnll->node->id, lnll->node->y,
	      lnll->node->indegree, lnll->node->outdegree);
      lnll = lnll->next;
    }

  extern void exit (int status);

  printf ("%s(): this are now the edges:\n", __func__);
  enl = g->edgelist;
  while (enl)
    {
      printf
	("  edge from gml node=%d to gml node=%d reversed=%d edge-length=%d\n",
	 enl->edge->from_node->id, enl->edge->to_node->id,
	 enl->edge->reversed,
	 (enl->edge->to_node->y - enl->edge->from_node->y));
      if ((enl->edge->to_node->y - enl->edge->from_node->y) < 0)
	{
	  printf ("%s(): shouldnothappen\n", __func__);
	  g->errorstatus = 1;
	}
      enl = enl->next;
    }

  return;
}

/***************************/

/* dfs check again and revers if needed */
void
edgelen (struct gml_graph *g)
{
  struct gml_elist *el = NULL;
  struct gml_edge *edge = NULL;
  struct gml_node *sn = NULL;
  struct gml_node *tn = NULL;
  struct gml_node *tmpnode = NULL;

  el = g->edgelist;

  while (el)
    {
      edge = el->edge;
      sn = edge->from_node;
      tn = edge->to_node;
      if (tn->y - sn->y < 0)
	{
	  if (yydebug)
	    {
	      printf
		("%s(): before splitting, edgelen < 0 from %d->%d level %d->%d\n",
		 __func__, sn->id, tn->id, sn->y, tn->y);
	    }

	  tmpnode = tn;
	  el->edge->to_node = el->edge->from_node;
	  el->edge->from_node = tmpnode;
	}

      el = el->next;
    }

  return;
}

/* try to find shorter edges */
void
shorteredges (struct gml_graph *g)
{
  struct gml_nlist *lnl = NULL;

  /* tmp patch */
  if (0)
    {
      return;
    }

  lnl = g->nodelist;

  while (lnl)
    {
      /* sometimes starter nodes can be moved close to to-node */
      if (lnl->node->indegree == 0)
	{
	  if (lnl->node->outdegree == 1)
	    {
	      /* this node can be moved closer to the target */
	      lnl->node->y = (lnl->node->outgoing_e->edge->to_node->y - 1);
	    }
	}
      lnl = lnl->next;
    }

  return;
}

/* doublespace the vertical levels */
void
doublespacey (struct gml_graph *g)
{
  struct gml_nlist *lnl = NULL;

  /* same edges now will have different dummy nodes resulting in 2 lines */
  maxlevel = 0;

  lnl = g->nodelist;

  while (lnl)
    {
      lnl->node->y = (2 * lnl->node->y);

      if (lnl->node->y > maxlevel)
	{
	  maxlevel = lnl->node->y;
	}

      lnl = lnl->next;
    }

  return;
}

/* split longer edges */
void
splitedges (struct gml_graph *g)
{
  struct gml_elist *el = NULL;
  struct gml_elist *elnext = NULL;
  struct gml_edge *edge = NULL;
  struct gml_node *sn = NULL;
  struct gml_node *tn = NULL;
  struct gml_node *nlnode = NULL;
  int edgelen = 0;
  int prevnodeid = 0;
  int newid = 0;
  int i = 0;
  int sny = 0;
  char rev = 0;
  int ecolor = 0;
  int style = 0;
  char *fc = NULL;
  char *tc = NULL;

  el = g->edgelist;

  while (el)
    {
      elnext = el->next;
      edge = el->edge;
      sn = edge->from_node;	/* from-node */
      tn = edge->to_node;	/* to-node */
      rev = edge->reversed;	/* edge attr. to copy when splitting edge */
      ecolor = edge->ecolor;	/* color of edge line */
      style = edge->style;
      fc = edge->fcompass;
      tc = edge->tcompass;

      edgelen = (tn->y - sn->y);

      /* horizontal edge */
      if (edgelen == 0)
	{
	  /* horizontal edge has original endpoints, used in drawing edges */
	  edge->hedge = 1;
	  g->nhedges++;		/* number of horizontal edges */
	  /* mark that nodes have a hor. edge */
	  sn->hashedge = 1;
	  tn->hashedge = 1;

	  if (0)
	    {
	      printf
		("%s(): horizontal edge %d->%d \"%s\"->\"%s\" rev=%d length %d pos=%d -> pos=%d\n",
		 __func__, sn->id, tn->id, sn->nlabel, tn->nlabel, rev,
		 edgelen, sn->x, tn->x);
	      fflush (stdout);
	    }

	}
      else if (edgelen > 1)
	{
	  if (yydebug)
	    {
	      printf ("%s(): splitting edge %d->%d length %d\n", __func__,
		      sn->id, tn->id, edgelen);
	      fflush (stdout);
	    }

	  prevnodeid = sn->id;
	  sny = sn->y;

	  for (i = 1; i < edgelen; i++)
	    {
	      /* dummy node numbers start at first free id number */
	      g->maxid = g->maxid + 1;
	      newid = g->maxid;
	      add_new_dummynode (g, newid);
	      nlnode = uniqnodeid (newid);
	      nlnode->dummy = 1;	/* this is a dummy node */
	      nlnode->elabel = 0;	/* not a edgelabel */
	      nlnode->y = (sny + i);
	      nlnode->startnode = sn->startnode;
	      add_new_dummyedge (g, prevnodeid, newid, rev, ecolor, style, fc,
				 tc);
	      prevnodeid = newid;
	    }

	  add_new_dummyedge (g, prevnodeid, tn->id, rev, ecolor, style, fc,
			     tc);
	  del_edge (g, el);
	}
      else if (edgelen == 1)
	{
	  /* edge len is 1 oke. */
	}
      else
	{
	  /* shouldnothappen */
	  printf ("%s(): edgelen<0 is %d shouldnothappen\n", __func__,
		  edgelen);
	  fflush (stdout);
	}

      el = elnext;
    }

  return;
}

/* create level node count data */
void
nodecounts (struct gml_graph *g)
{
  struct gml_nlist *lnl = NULL;

  /* refresh st lists */
  clear_stlist_all (g);
  make_stlist (g);
  nlevels = maxlevel + 1;

  /* table with number of nodes per level */
  nnodes_of_level = calloc (nlevels, sizeof (int));

  if (nnodes_of_level == NULL)
    {
      return;
    }

  /* determine widest level and how many nodes it has */
  widestlevel = 0;
  widestnnodes = 0;

  lnl = g->nodelist;
  while (lnl)
    {
      /* rely used for sugi */
      lnl->node->rely = lnl->node->y;

      nnodes_of_level[lnl->node->y] = nnodes_of_level[lnl->node->y] + 1;

      /* x used for sugi, offset 1...n */
      lnl->node->relx = nnodes_of_level[lnl->node->y];

      if (nnodes_of_level[lnl->node->y] >= widestnnodes)
	{
	  widestnnodes = nnodes_of_level[lnl->node->y];
	  widestlevel = lnl->node->y;
	}

      lnl = lnl->next;
    }

  return;
}


/* this is called from the parsercode.
 * the parser has already done some checks.
 */
void
add_new_edge (struct gml_graph *g, int foundsource,
	      int foundtarget, char *elabel, int ecolor, int style,
	      char *fcompass, char *tcompass)
{
  struct gml_node *snode = NULL;
  struct gml_node *tnode = NULL;
  struct gml_edge *edge = NULL;
  struct gml_edge *edge2 = NULL;
  struct gml_elist *el = NULL;

  /* get node struct of sourcenode */
  snode = uniqnodeid (foundsource);
  tnode = uniqnodeid (foundtarget);

  if (snode == NULL)
    {
      printf
	("%s(): source node in edge from %d to %d not found and edge is skipped\n",
	 __func__, foundsource, foundtarget);
    }



  if (tnode == NULL)
    {
      printf
	("%s(): target node in edge from %d to %d not found and edge is skipped\n",
	 __func__, foundsource, foundtarget);
    }

  if ((snode == NULL) || (tnode == NULL))
    {
      return;
    }

  /* at self edge incr. it at the node */
  if (snode == tnode)
    {
      /* a self-edge, increment count */
      snode->nselfedges++;
      g->nselfedges++;
      /* add node in list with self-edge nodes */
      add_selfedgenode (g, snode);
    }
  else
    {
      /* a new edge */
      edge = calloc (1, sizeof (struct gml_edge));

      if (edge == NULL)
	{
	  return;
	}

      g->edgenum++;
      edge->nr = g->edgenum;
      edge->from_node = snode;
      edge->to_node = tnode;
      edge->elabel = elabel;
      edge->ecolor = ecolor;
      edge->style = style;
      edge->fcompass = fcompass;
      edge->tcompass = tcompass;

      /* update number of edgelabels in the graph */
      if (elabel)
	{
	  g->nedgelabels++;
	}

      el = calloc (1, sizeof (struct gml_elist));

      if (el == NULL)
	{
	  free (edge);
	  return;
	}

      el->edge = edge;
      if (g->edgelist == NULL)
	{
	  g->edgelist = el;
	  g->edgelisttail = el;
	}
      else
	{
	  g->edgelisttail->next = el;
	  g->edgelisttail = el;
	}

    }

  /* add to raw edgelist */
  edge2 = calloc (1, sizeof (struct gml_edge));

  if (edge2 == NULL)
    {
      return;
    }

  edge2->nr = g->edgenum;
  edge2->from_node = snode;
  edge2->to_node = tnode;
  edge2->elabel = elabel;
  edge2->ecolor = ecolor;
  edge2->style = style;
  edge2->fcompass = fcompass;
  edge2->tcompass = tcompass;

  el = calloc (1, sizeof (struct gml_elist));

  if (el == NULL)
    {
      free (edge2);
      return;
    }

  el->edge = edge2;

  if (g->rawedgelist == NULL)
    {
      g->rawedgelist = el;
      g->rawedgelisttail = el;
    }
  else
    {
      g->rawedgelisttail->next = el;
      g->rawedgelisttail = el;
    }


  g->nedges++;

  return;
}

/* edge to dummy node is in edgelist but not in rawedgelist */
void
add_new_dummyedge (struct gml_graph *g, int foundsource,
		   int foundtarget, int reversed, int ecolor, int style,
		   char *fcompass, char *tcompass)
{
  struct gml_node *snode = NULL;
  struct gml_node *tnode = NULL;
  struct gml_edge *edge = NULL;
  struct gml_elist *el = NULL;

  snode = uniqnodeid (foundsource);

  if (snode == NULL)
    {
      printf ("sourcenode in %d->%d not found\n", foundsource, foundtarget);
      return;
    }


  tnode = uniqnodeid (foundtarget);

  if (tnode == NULL)
    {
      printf ("targetnode in %d->%d not found\n", foundsource, foundtarget);
      return;
    }


  edge = calloc (1, sizeof (struct gml_edge));

  if (edge == NULL)
    {
      return;
    }

  edge->from_node = snode;	/* from-node */
  edge->to_node = tnode;	/* to-node */
  edge->reversed = reversed;	/* edge attr. edge-is-reversed */
  edge->ecolor = ecolor;	/* r/g/b of edge line */
  edge->style = style;
  edge->fcompass = fcompass;
  edge->tcompass = tcompass;

  el = calloc (1, sizeof (struct gml_elist));

  if (el == NULL)
    {
      return;
    }

  el->edge = edge;

  if (g->edgelist == NULL)
    {
      g->edgelist = el;
      g->edgelisttail = el;
    }
  else
    {
      g->edgelisttail->next = el;
      g->edgelisttail = el;
    }

  return;
}


/* this is called from the parser code to add a node
 * the parsercode has already done some checks.
 */
void
add_new_node (struct gml_graph *g, int foundid, char *nodelabel, int ncolor,
	      struct gml_rl *rlabel)
{
  struct gml_node *node = NULL;
  struct gml_node *node2 = NULL;
  struct gml_nlist *lnl = NULL;
  char nlbuf[16];
  char *lb = NULL;

  node = uniqnodeid (foundid);

  if (node)
    {
      if (nodelabel)
	{
	  lb = nodelabel;
	}
      else
	{
	  lb = "";
	}
      printf
	("%s(): node id %d with label \"%s\"is already defined and this one skipped\n",
	 __func__, foundid, lb);
      if (node->nlabel)
	{
	  lb = node->nlabel;
	}
      else
	{
	  lb = "";
	}
      printf
	("%s(): earlier defined as node %d with label \"%s\"\n", __func__,
	 node->id, lb);
      return;
    }

  if (g->maxid <= foundid)
    {
      g->maxid = foundid;
    }

  /* label is node number or specified label */
  if (nodelabel == NULL)
    {
      memset (nlbuf, 0, 16);
      /* no specified node label, so use the id of the node. */
      snprintf (nlbuf, (16 - 1), "%d", foundid);
    }

  node = calloc (1, sizeof (struct gml_node));

  if (node == NULL)
    {
      return;
    }

  node->rlabel = rlabel;	/* record label */

  node->id = foundid;		/* id of node */
  node->ncolor = ncolor;	/* fill color r/g/b */

  if (nodelabel)
    {
      /* label is the specified label */
      node->nlabel = nodelabel;
    }
  else
    {
      /* label is the numeric string of the node id. */
      node->nlabel = uniqstr (nlbuf);
    }

  /* uniq node numbers start at 1 */
  g->nodenum++;

  node->nr = g->nodenum;
  uniqnode_add (node);

  lnl = calloc (1, sizeof (struct gml_nlist));

  if (lnl == NULL)
    {
      free (node);
      return;
    }

  lnl->node = node;

  if (g->nodelist == NULL)
    {
      g->nodelist = lnl;
      g->nodelisttail = lnl;
    }
  else
    {
      g->nodelisttail->next = lnl;
      g->nodelisttail = lnl;
    }


  /* add to raw list */
  node2 = calloc (1, sizeof (struct gml_node));

  if (node2 == NULL)
    {
      return;
    }

  node2->rlabel = rlabel;	/* record label */

  node2->id = foundid;
  node2->ncolor = ncolor;	/* fill color r/g/b */

  if (nodelabel)
    {
      node2->nlabel = nodelabel;
    }
  else
    {
      node2->nlabel = uniqstr (nlbuf);
    }

  /* uniq node numbers start at 1 */
  node2->nr = g->nodenum;

  lnl = calloc (1, sizeof (struct gml_nlist));

  if (lnl == NULL)
    {
      free (node2);
      return;
    }

  lnl->node = node2;

  if (g->rawnodelist == NULL)
    {
      g->rawnodelist = lnl;
      g->rawnodelisttail = lnl;
    }
  else
    {
      g->rawnodelisttail->next = lnl;
      g->rawnodelisttail = lnl;
    }

  g->nnodes++;

  return;
}

/* dummy nodes are only in nodelist, not raw nodelist */
void
add_new_dummynode (struct gml_graph *g, int foundid)
{
  struct gml_node *node = NULL;
  struct gml_nlist *lnl = NULL;

  if (uniqnodeid (foundid))
    {
      printf ("%s(): node %d already defined\n", __func__, foundid);
      fflush (stdout);
      return;
    }

  if (g->maxid <= foundid)
    {
      g->maxid = foundid;
    }

  node = calloc (1, sizeof (struct gml_node));

  if (node == NULL)
    {
      return;
    }

  node->id = foundid;

  /*  white background color for edgelabel */
  node->ncolor = 0xffffffff;

  /* uniq node numbers start at 1 */
  g->nodenum++;

  node->nr = g->nodenum;
  uniqnode_add (node);

  lnl = calloc (1, sizeof (struct gml_nlist));

  if (lnl == NULL)
    {
      return;
    }

  lnl->node = node;

  if (g->nodelist == NULL)
    {
      g->nodelist = lnl;
    }
  else
    {
      g->nodelisttail->next = lnl;
    }

  g->nodelisttail = lnl;

  return;
}

/* lists per position */
void
make_posnodes (struct gml_graph *g)
{
  struct gml_nlist *lnl = NULL;
  struct gml_nlist *newl = NULL;
  int i = 0;
  int maxw = 0;
  int maxrx = 0;

  /* extra check max rel. x pos. */
  lnl = g->nodelist;

  while (lnl)
    {
      if (lnl->node->absx > maxrx)
	{
	  maxrx = lnl->node->absx;
	}
      lnl = lnl->next;
    }

  /* pos.c has moved node in x dir. */
  if (maxrx > widestnnodes)
    {
      widestnnodes = maxrx;
    }

  /* x width at position */
  wpos = calloc (1, (widestnnodes + 1) * sizeof (int));

  if (wpos == NULL)
    {
      return;
    }

  /* lists with nodes up to down at position */
  posnodes = calloc (1, (widestnnodes + 1) * sizeof (struct gml_nlist *));

  if (posnodes == NULL)
    {
      return;
    }

  /* create for every postion the list of nodes at that position */
  lnl = g->nodelist;
  while (lnl)
    {
      i = lnl->node->absx;

      newl = calloc (1, sizeof (struct gml_nlist));

      if (newl == NULL)
	{
	  return;
	}

      newl->node = lnl->node;

      if (posnodes[i] == NULL)
	{
	  posnodes[i] = newl;
	  newl->next = NULL;
	}
      else
	{
	  newl->next = posnodes[i];
	  posnodes[i] = newl;
	}

      lnl = lnl->next;
    }

  /* determine the max width of a element at vertical pos. */
  for (i = 0; i < (widestnnodes + 1); i++)
    {
      maxw = 0;

      /* lists per pos. */
      lnl = posnodes[i];

      while (lnl)
	{
	  if (lnl->node->bbx > maxw)
	    {
	      maxw = lnl->node->bbx;
	    }
	  lnl = lnl->next;
	}

      wpos[i] = maxw;

      if (0)
	{
	  printf ("x-position %d has max xsize %d\n", i, maxw);
	}

    }

  return;
}


/* clear pos. nodes lists */
void
clear_posnodes (struct gml_graph *g)
{
  int i = 0;
  struct gml_nlist *lnl = NULL;
  struct gml_nlist *nlnext = NULL;

  if (g)
    {
    }

  /* width of positions */
  if (wpos)
    {
      free (wpos);
      wpos = NULL;
    }

  for (i = 0; i < (widestnnodes + 1); i++)
    {
      /* lists per pos. */
      lnl = posnodes[i];

      while (lnl)
	{
	  nlnext = lnl->next;
	  free (lnl);
	  lnl = nlnext;
	}

      posnodes[i] = NULL;
    }

  free (posnodes);
  posnodes = NULL;

  return;
}

/* lists per level */
void
make_levelnodes (struct gml_graph *g)
{
  struct gml_nlist *lnl = NULL;
  struct gml_nlist *newl = NULL;
  int i = 0;
  int maxh = 0;

  hpos = calloc (1, (maxlevel + 1) * sizeof (int));

  if (hpos == NULL)
    {
      return;
    }

  levelnodes = calloc (1, (maxlevel + 1) * sizeof (struct gml_nlist *));

  if (levelnodes == NULL)
    {
      return;
    }

  lnl = g->nodelist;

  while (lnl)
    {
      i = lnl->node->absy;

      newl = calloc (1, sizeof (struct gml_nlist));

      if (newl == NULL)
	{
	  return;
	}

      newl->node = lnl->node;

      if (levelnodes[i] == NULL)
	{
	  levelnodes[i] = newl;
	  newl->next = NULL;
	}
      else
	{
	  newl->next = levelnodes[i];
	  levelnodes[i] = newl;
	}

      lnl = lnl->next;
    }

  /* determine the max width of a element at vertical pos. */
  for (i = 0; i < (maxlevel + 1); i++)
    {

      maxh = 0;

      /* lists per pos. */
      lnl = levelnodes[i];

      while (lnl)
	{
	  if (lnl->node->bby > maxh)
	    {
	      maxh = lnl->node->bby;
	    }
	  lnl = lnl->next;
	}

      hpos[i] = maxh;
    }

  return;
}

/* clear level nodes lists */
void
clear_levelnodes (struct gml_graph *g)
{
  int i = 0;
  struct gml_nlist *lnl = NULL;
  struct gml_nlist *nlnext = NULL;

  if (g)
    {
    }

  /* width of positions */
  if (hpos)
    {
      free (hpos);
      hpos = NULL;
    }

  for (i = 0; i < (maxlevel + 1); i++)
    {
      /* lists per pos. */
      lnl = levelnodes[i];
      while (lnl)
	{
	  nlnext = lnl->next;
	  free (lnl);
	  lnl = nlnext;
	}

      levelnodes[i] = NULL;
    }

  free (levelnodes);
  levelnodes = NULL;

  return;
}

/* clear table of startnodes */
void
clear_startnodes (struct gml_graph *g)
{

  if (g->startnodes)
    {
      free (g->startnodes);
      g->startnodes = NULL;
    }

  g->startnodes = NULL;
  g->nstartnodes = 0;

  return;
}

/* end */
